package com.zlk.algorithm.algorithm.sort.heap;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
/**
 * @program: algorithm
 * @ClassName HeapGreaterTest
 * @description:
 * @author: slfang
 * @create: 2024-11-21 16:33
 * @Version 1.0
 **/
public class HeapGreaterTest<T> {


    List<T> heap ;
    HashMap<T,Integer> indexMap ;
    int size ;
    Comparator<T> comparator;

    public HeapGreaterTest(Comparator comparator){
        heap = new ArrayList<>();
        indexMap = new HashMap<>();
        size = 0;
        this.comparator = comparator;
    }





    //插入上浮
    public void up(T t){
//        int index = size;
//        if(indexMap.containsKey(t)){
//            resigen(t);
//        }else{
//            indexMap.put(t,size++);
//
//        }
        int index = indexOf(t);
        while (comparator.compare(heap.get(index),heap.get(index-1/2))>0){
            index = index-1/2;
            sweap(index,index-1/2);
        }
    }

    private void sweap(int i, int j) {
        T iVal = heap.get(i);
        T jVal = heap.get(j);
        Integer indexI = indexMap.get(iVal);
        Integer indexJ = indexMap.get(jVal);
        heap.set(i,jVal);
        heap.set(j,iVal);
        indexMap.put(iVal,indexJ);
        indexMap.put(jVal,indexI);
    }

    //下浮
    public void down(T t){

    }

    //属性变动重新堆化
    public void resigen(T t){
        int index = indexOf(t);
        up(t);
        down(t);
    }

    void push(T t){
        if(indexMap.containsKey(t)){
            resigen(t);
        }else{
            indexMap.put(t,size++);
            up(t);
        }
    }



    //查找属性存在的位置
    private int indexOf(T t) {
        return indexMap.get(t);
    }


}
